/*
2021-11-12
https://leetcode-cn.com/problems/check-if-an-original-string-exists-given-two-encoded-strings/
*/
const int N = 41, M = 2001;
const int offset = 1000;

bool isnum(char c){ return c>='0'&&c<='9'; }
bool ischar(char c) {return c>='a' && c<='z';}

class Solution {
private:
    bool f[N][N][M];
public:
    bool possiblyEquals(string s1, string s2) {
        int n=s1.size(),m=s2.size();
        f[0][0][offset]=1;

        for(int i=0;i<=n;i++)
            for(int j=0;j<=m;j++)
                for(int k=0;k<=2000;k++)
                {
                    if(!f[i][j][k]) continue;
                    if(k==offset && i<n && j<=m && s1[i]==s2[j]) 
                        f[i+1][j+1][k]=true;
                    if(k>offset && j<m && ischar(s2[j]))
                        f[i][j+1][k-1]=true;
                    if(k<offset && i<n && ischar(s1[i]))
                        f[i+1][j][k+1]=true;
                    int v=0;
                    for(int u=i;u<n && isnum(s1[u]);u++)
                    {
                        v=v*10+s1[u]-'0';
                        if(v+k<2000)
                            f[u+1][j][v+k]=true;
                    }
                    v=0;
                    for(int u=j;u<m && isnum(s2[u]);u++)
                    {
                        v=v*10+s2[u]-'0';
                        if(k>=v)
                            f[i][u+1][k-v]=true;
                    }
                }

        return f[n][m][offset];
    }
};
